# -*- coding: utf-8 -*-
"""
Created on Fri Dec 21 16:04:29 2018

@author: Administrator
"""
import sys
sys.path.append("../queue/")

from prior_queue import ListPriorQueue
from seq_queue import SeqQueue
from tree_node import BTNode

class HTNode(BTNode):
    def __lt__(self, other_node):
        """重载运算符 <
        """
        return self.data < other_node.data
    
    def __gt__(self, other_node):
        """重载运算符 >
        """
        return self.data > other_node.data

    def __le__(self, other_node):
        """重载运算符 <=
        """
        return self.data <= other_node.data
    
    def __ge__(self, other_node):
        """重载运算符 >=
        """
        return self.data >= other_node.data
    
class HuffmanTree:
    """链式霍夫曼树
    使用链式实现霍夫曼树
    """
    def __init__(self, root = None):
        self.root = root
        
    def create(self, weights):
        # 使用优先队列用于节点排序
        queue = ListPriorQueue()
        for weight in weights:
            queue.enqueue(HTNode(weight))
        # 构造huffman tree
        while queue.length > 1:
            t1 = queue.dequeue()
            t2 = queue.dequeue()
            new_data = t1.data + t2.data
            queue.enqueue(BTNode(new_data, t1, t2))     # 组成新霍夫曼树
        self.root = queue.dequeue()
        
    def levelorder(self):
        """层次遍历
        """
        queue = SeqQueue()
        queue.enqueue(self.root)
        while not queue.is_empty():
            temp = queue.dequeue()
            print(temp.data)
            if temp.left is not None:
                queue.enqueue(temp.left)
            if temp.right is not None:
                queue.enqueue(temp.right)
                